#include <pmm.h>
#include <list.h>
#include <string.h>
#include <default_pmm.h>
#include <stdio.h>

/* In the first fit algorithm, the allocator keeps a list of free blocks (known as the free list) and,
   on receiving a request for memory, scans along the list for the first block that is large enough to
   satisfy the request. If the chosen block is significantly larger than that requested, then it is 
   usually split, and the remainder added to the list as another free block.
   Please see Page 196~198, Section 8.2 of Yan Wei Min's chinese book "Data Structure -- C programming language"
*/
// you should rewrite functions: default_init,default_init_memmap,default_alloc_pages, default_free_pages.
/*
 * Details of FFMA
 * (1) Prepare: In order to implement the First-Fit Mem Alloc (FFMA), we should manage the free mem block use some list.
 *              The struct free_area_t is used for the management of free mem blocks. At first you should
 *              be familiar to the struct list in list.h. struct list is a simple doubly linked list implementation.
 *              You should know howto USE: list_init, list_add(list_add_after), list_add_before, list_del, list_next, list_prev
 *              Another tricky method is to transform a general list struct to a special struct (such as struct page):
 *              you can find some MACRO: le2page (in memlayout.h), (in future labs: le2vma (in vmm.h), le2proc (in proc.h),etc.)
 * (2) default_init: you can reuse the  demo default_init fun to init the free_list and set nr_free to 0.
 *              free_list is used to record the free mem blocks. nr_free is the total number for free mem blocks.
 * (3) default_init_memmap:  CALL GRAPH: kern_init --> pmm_init-->page_init-->init_memmap--> pmm_manager->init_memmap
 *              This fun is used to init a free block (with parameter: addr_base, page_number).
 *              First you should init each page (in memlayout.h) in this free block, include:
 *                  p->flags should be set bit PG_property (means this page is valid. In pmm_init fun (in pmm.c),
 *                  the bit PG_reserved is setted in p->flags)//p->flags是设置PG_reserved和property
 *                  if this page  is free and is not the first page of free block, p->property should be set to 0.
 *                  if this page  is free and is the first page of free block, p->property should be set to total num of block.
 *                  p->ref should be 0, because now p is free and no reference.
 *                  We can use p->page_link to link this page to free_list, (such as: list_add_before(&free_list, &(p->page_link)); )
 *              Finally, we should sum the number of free mem block: nr_free+=n
 * (4) default_alloc_pages: search find a first free block (block size >=n) in free list and reszie the free block, return the addr
 *              of malloced block.
 *              (4.1) So you should search freelist like this:
 *                       list_entry_t le = &free_list;
 *                       while((le=list_next(le)) != &free_list) {
 *                       ....
 *                 (4.1.1) In while loop, get the struct page and check the p->property (record the num of free block) >=n?
 *                       struct Page *p = le2page(le, page_link);
 *                       if(p->property >= n){ ...
 *                 (4.1.2) If we find this p, then it' means we find a free block(block size >=n), and the first n pages can be malloced.
 *                     Some flag bits of this page should be setted: PG_reserved =1, PG_property =0
 *                     unlink the pages from free_list
 *                     (4.1.2.1) If (p->property >n), we should re-caluclate number of the the rest of this free block,
 *                           (such as: le2page(le,page_link))->property = p->property - n;)
 *                 (4.1.3)  re-caluclate nr_free (number of the the rest of all free block)
 *                 (4.1.4)  return p
 *               (4.2) If we can not find a free block (block size >=n), then return NULL
 * (5) default_free_pages: relink the pages into  free list, maybe merge small free blocks into big free blocks.
 *               (5.1) according the base addr of withdrawed blocks, search free list, find the correct position
 *                     (from low to high addr), and insert the pages. (may use list_next, le2page, list_add_before)
 *               (5.2) reset the fields of pages, such as p->ref, p->flags (PageProperty)
 *               (5.3) try to merge low addr or high addr blocks. Notice: should change some pages's p->property correctly.
 */
free_area_t free_area;//存放list_header 和 空闲page 数目

#define free_list (free_area.free_list)
#define nr_free (free_area.nr_free)

static void
default_init(void) {
    list_init(&free_list);//初始化了一个空链表free list用来管理free page
    nr_free = 0;
}
//初始化内存块
/*
1.初始化n个page
2.设置head page的PageProperty标志，更新其property，和free list中的free page数
3.按照地址大小顺序将初始化的free page插入free list

*/
static void
default_init_memmap(struct Page *base, size_t n) {
    assert(n > 0);//检测n是否>0；assert(expr)；当expr为假时终止程序
    struct Page *p = base;//声明起始为base的page
    for (; p != base + n; p ++) {//初始化n个page
        assert(PageReserved(p));//page是保留页
        p->flags = p->property = 0;//设置标志位为0（可以被分配）（不是head page）
        set_page_ref(p, 0);//page被引用的次数设置为0
    }
    base->property = n;//head page 处更改property：从此处开始连续n个free page
    SetPageProperty(base);//设置base是head page（可被分配）
    nr_free += n;//free list 中free page的数目+n
    if (list_empty(&free_list)) {
        list_add(&free_list, &(base->page_link));//如果free list为空，直接add
    } else {//free list非空
        list_entry_t* le = &free_list;
        while ((le = list_next(le)) != &free_list) {
            struct Page* page = le2page(le, page_link);//得到free list中已有的非链表尾的free page首地址
            //按地址顺序插入free list
            if (base < page) {
                list_add_before(le, &(base->page_link));//free list插入free page（在当前项le前）
                break;//插入后结束循环
            } else if (list_next(le) == &free_list) {
                list_add(le, &(base->page_link));//free page插到链表尾
            }
        }
    }
}
//分配大小为n page的free block
/*
1. 判断剩余空间是否足够
2.若足够，在free list中找到第一个满足分配需求的page
3.若该page分配后仍有空余，则将剩余free page加入free list，并更新head page和对应的PageProperty
4.更新free list中的free page数量，清空旧head page的Pageproperty位

*/
static struct Page *
default_alloc_pages(size_t n) {
    assert(n > 0);
    if (n > nr_free) {
        return NULL;//空闲空间不够分配
    }
    struct Page *page = NULL;
    list_entry_t *le = &free_list;
    while ((le = list_next(le)) != &free_list) {
        struct Page *p = le2page(le, page_link);
        if (p->property >= n) {
            page = p;//得到free list中具有足够空闲空间的页
            break;//结束
        }
    }
    if (page != NULL) {//如果存在满足的page
        list_entry_t* prev = list_prev(&(page->page_link));//拿到page的前向free page
        list_del(&(page->page_link));//从free list中删除该页
        //如果分配后还有空余；将分配后的剩余部分重新插入free list
        if (page->property > n) {
            struct Page *p = page + n;//得到空闲的首地址
            p->property = page->property - n;//分配出去
            SetPageProperty(p);//重新设置新p为head page(声明page可被分配)
            list_add(prev, &(p->page_link));//把剩余的free page链接进空闲链表
        }
        nr_free -= n;//更新free list中的free page数量
        ClearPageProperty(page);//将原来的整个块的head page标记位清空
    }
    return page;
}
//释放page
/*
1.将要释放的page中的置位与引用次数清空
2.根据释放大小更新nr_free,确定释放的head page
3.将释放的free page按照地址大小加入链表
4.合并与之相邻的可合并的free page并更新相应参数
*/
static void
default_free_pages(struct Page *base, size_t n) {
    assert(n > 0);
    struct Page *p = base;//要释放的page首地址
    for (; p != base + n; p ++) {
        assert(!PageReserved(p) && !PageProperty(p));//说明已经被分配
        p->flags = 0;//清空标志位，（声明page是可被分配且不是head page）
        set_page_ref(p, 0);//清空被引用的次数
    }
    base->property = n;//确定释放大小
    SetPageProperty(base);//设置base为释放后的head page
    nr_free += n;//更新free list中的free page数量


    //将释放的page按照地址顺序插入free list
    if (list_empty(&free_list)) {
        list_add(&free_list, &(base->page_link));
    } else {
        list_entry_t* le = &free_list;
        while ((le = list_next(le)) != &free_list) {
            struct Page* page = le2page(le, page_link);
            if (base < page) {
                list_add_before(le, &(base->page_link));
                break;
            } else if (list_next(le) == &free_list) {
                list_add(le, &(base->page_link));
            }
        }
    }

    //合并释放的page与free list中的相邻page{前向page和后向page}

    list_entry_t* le = list_prev(&(base->page_link));//free list中已释放page的前向page
    if (le != &free_list) {//已经释放的page的前向page不是free list的首地址
        p = le2page(le, page_link);//得到该page
        if (p + p->property == base) {//如果前向page+前向page内的free page==已释放的page首地址（说明已释放的page可以和前一个free page进行合并）
            p->property += base->property;//更新前向page的property（合并两个free page）
            ClearPageProperty(base);//清除已释放page的标志位
            list_del(&(base->page_link));//再把旧的已释放的page从free list中删除
            base = p;//更新合并后的free page的首地址为前向page的首地址
        }
    }

    le = list_next(&(base->page_link));
    if (le != &free_list) {//已经释放的page的后向page不是free list的首地址
        p = le2page(le, page_link);
        if (base + base->property == p) {//如果已释放page的首地址+该page中的free page=后向page的首地址（说明已释放的page可以和后一个free page进行合并）
        /*合并操作
        1.更新地址小的head page的property
        2.清除地址大的head page的标志位（声明不再是head page）
        3.从free list中删除地址大的head page为首的空闲块
        */
            base->property += p->property;
            ClearPageProperty(p);
            list_del(&(p->page_link));
        }
    }
}

static size_t
default_nr_free_pages(void) {
    return nr_free;
}

static void
basic_check(void) {
    struct Page *p0, *p1, *p2;
    p0 = p1 = p2 = NULL;
    assert((p0 = alloc_page()) != NULL);
    assert((p1 = alloc_page()) != NULL);
    assert((p2 = alloc_page()) != NULL);

    assert(p0 != p1 && p0 != p2 && p1 != p2);
    assert(page_ref(p0) == 0 && page_ref(p1) == 0 && page_ref(p2) == 0);

    assert(page2pa(p0) < npage * PGSIZE);
    assert(page2pa(p1) < npage * PGSIZE);
    assert(page2pa(p2) < npage * PGSIZE);

    list_entry_t free_list_store = free_list;
    list_init(&free_list);
    assert(list_empty(&free_list));

    unsigned int nr_free_store = nr_free;
    nr_free = 0;

    assert(alloc_page() == NULL);

    free_page(p0);
    free_page(p1);
    free_page(p2);
    assert(nr_free == 3);

    assert((p0 = alloc_page()) != NULL);
    assert((p1 = alloc_page()) != NULL);
    assert((p2 = alloc_page()) != NULL);

    assert(alloc_page() == NULL);

    free_page(p0);
    assert(!list_empty(&free_list));

    struct Page *p;
    assert((p = alloc_page()) == p0);
    assert(alloc_page() == NULL);

    assert(nr_free == 0);
    free_list = free_list_store;
    nr_free = nr_free_store;

    free_page(p);
    free_page(p1);
    free_page(p2);
}

// LAB2: below code is used to check the first fit allocation algorithm
// NOTICE: You SHOULD NOT CHANGE basic_check, default_check functions!
static void
default_check(void) {
    int count = 0, total = 0;
    list_entry_t *le = &free_list;
    while ((le = list_next(le)) != &free_list) {
        struct Page *p = le2page(le, page_link);
        assert(PageProperty(p));
        count ++, total += p->property;
    }
    assert(total == nr_free_pages());

    basic_check();

    struct Page *p0 = alloc_pages(5), *p1, *p2;
    assert(p0 != NULL);
    assert(!PageProperty(p0));

    list_entry_t free_list_store = free_list;
    list_init(&free_list);
    assert(list_empty(&free_list));
    assert(alloc_page() == NULL);

    unsigned int nr_free_store = nr_free;
    nr_free = 0;

    free_pages(p0 + 2, 3);
    assert(alloc_pages(4) == NULL);
    assert(PageProperty(p0 + 2) && p0[2].property == 3);
    assert((p1 = alloc_pages(3)) != NULL);
    assert(alloc_page() == NULL);
    assert(p0 + 2 == p1);

    p2 = p0 + 1;
    free_page(p0);
    free_pages(p1, 3);
    assert(PageProperty(p0) && p0->property == 1);
    assert(PageProperty(p1) && p1->property == 3);

    assert((p0 = alloc_page()) == p2 - 1);
    free_page(p0);
    assert((p0 = alloc_pages(2)) == p2 + 1);

    free_pages(p0, 2);
    free_page(p2);

    assert((p0 = alloc_pages(5)) != NULL);
    assert(alloc_page() == NULL);

    assert(nr_free == 0);
    nr_free = nr_free_store;

    free_list = free_list_store;
    free_pages(p0, 5);

    le = &free_list;
    while ((le = list_next(le)) != &free_list) {
        struct Page *p = le2page(le, page_link);
        count --, total -= p->property;
    }
    assert(count == 0);
    assert(total == 0);
}
//这个结构体在
const struct pmm_manager default_pmm_manager = {
    .name = "default_pmm_manager",
    .init = default_init,
    .init_memmap = default_init_memmap,
    .alloc_pages = default_alloc_pages,
    .free_pages = default_free_pages,
    .nr_free_pages = default_nr_free_pages,
    .check = default_check,
};

